#include <iostream>
#include <algorithm>
#include "pentominoes.h"
#include "puzzles.h"

pentomino F(f_shape);
pentomino I(i_shape);
pentomino L(l_shape);
pentomino N(n_shape);
pentomino P(p_shape);
pentomino T(t_shape);
pentomino U(u_shape);
pentomino V(v_shape);
pentomino W(w_shape);
pentomino X(x_shape);
pentomino Y(y_shape);
pentomino Z(z_shape);

pentomino::pentomino(pentomino_map& pb)
{
	size = PENTO_SIZE;
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			bitmap[i][j] = pb[i][j];
}

pentomino::~pentomino()
{
}

char pentomino::at(int i, int j)
{
	return bitmap[i][j];
}

void pentomino::set(int i, int j, char val)
{
	bitmap[i][j] = val;
}	

bool pentomino::identical(pentomino &p)
{
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			if (at(i, j) != p.at(i, j))
				return false;
	return true;	
}

void pentomino::print()
{
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			if (bitmap[i][j] != ' ')
				cout << bitmap[i][j] << " ";
			else
				cout << "? ";
		cout << endl;
	}
}

pentomino& pentomino::copy()
{
	pentomino *p = new pentomino(bitmap);
	return *p;	
}

// dx, dy > 0
pentomino& pentomino::translate(int dx, int dy)
{
	pentomino *tp = new pentomino(bitmap);

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			tp->set(i, j, ' ');

	for (int i = dy; i <= size - 1; i++)
		for (int j = dx; j <= size - 1; j++)
			tp->set(i, j, at(i - dy, j - dx));

	return *tp;
}

pentomino& pentomino::reflect()
{
	pentomino *rp = new pentomino(bitmap);

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			rp->set(i, j, at(i, size - 1 - j));

	return *rp;
}

pentomino& pentomino::rotate90()
{
	pentomino *rp90 = new pentomino(bitmap);

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			rp90->set(i, j, at(j, size - 1 - i));

	return *rp90;
}

pentomino& pentomino::rotate90_n(int n)
{
	if (n == 1)
		return rotate90();
	else
		return rotate90_n(n - 1).rotate90();
}

void pentomino::orientations(vector<pentomino>& orient)
{
	pentomino& t = *this;
	pentomino& r = reflect();

	orient.push_back(t);
	orient.push_back(t.rotate90_n(1));
	orient.push_back(t.rotate90_n(2));
	orient.push_back(t.rotate90_n(3));

	orient.push_back(r);
	orient.push_back(r.rotate90_n(1));
	orient.push_back(r.rotate90_n(2));
	orient.push_back(r.rotate90_n(3));
}

bool operator==(const coord& x, const coord& y)
{
	return x.first == y.first && x.second == y.second;
}

puzzle::puzzle(puzzle_bitmap &pb, int r, int c, vector<pentomino>& sh)
{
	rows = r;
	cols = c;
	shapes = sh;
	for (int i = 0; i < rows; i++)
		for (int j = 0; j < cols; j++)
			bitmap[i][j] = pb[i][j];
}

puzzle::~puzzle()
{
}

bool puzzle::inside(int i, int j)
{
	return (0 <= i && i <= PUZZLE_ROWS - 1 &&
			0 <= j && j <= PUZZLE_COLS - 1);
}

void puzzle::neighbors(int i, int j, puzzle_bitmap& pb, vector<coord>& n)
{
	if (inside(i - 1, j) && pb[i - 1][j] != ' ' && 
			find(n.begin(), n.end(), make_pair(i - 1, j)) == n.end()) 
	{
		n.push_back(make_pair(i - 1, j));
		pb[i - 1][j] = ' ';
		neighbors(i - 1, j, pb, n);
	}

	if (inside(i, j - 1) && pb[i][j - 1] != ' ' && 
			find(n.begin(), n.end(), make_pair(i, j - 1)) == n.end())
	{
		n.push_back(make_pair(i, j - 1));
		pb[i][j - 1] = ' ';
		neighbors(i, j - 1, pb, n);
	}

	if (inside(i, j + 1) && pb[i][j + 1] != ' ' && 
			find(n.begin(), n.end(), make_pair(i, j + 1)) == n.end())
	{
		n.push_back(make_pair(i, j + 1));
		pb[i][j + 1] = ' ';
		neighbors(i, j + 1, pb, n);
	}

	if (inside(i + 1, j) && pb[i + 1][j] != ' ' && 
			find(n.begin(), n.end(), make_pair(i + 1, j)) == n.end())
	{
		n.push_back(make_pair(i + 1, j));
		pb[i + 1][j] = ' ';
		neighbors(i + 1, j, pb, n);
	}
}

bool puzzle::done(vector<coord>& filled)
{
	for (int i = 0; i < rows; i++)
		for (int j = 0; j < cols; j++) 
			if (bitmap[i][j] == '#') 
			{
				const coord c = make_pair(i, j);
				if (find(filled.begin(), filled.end(), c) == 
						filled.end())
					return false;
			}
	return true;
}

bool puzzle::eval(pentomino p, int x, int y, vector<coord>& filled)
{
	puzzle_bitmap pb;

	for (int i = 0; i < PUZZLE_ROWS; i++)
		for (int j = 0; j < PUZZLE_COLS; j++)
			pb[i][j] = bitmap[i][j];

	// fill all positions already taken up by pentominoes
	for (int i = 0; i < filled.size(); i++)
		pb[filled.at(i).first][filled.at(i).second] = ' ';

	for (int i = 0; i < PENTO_SIZE; i++)
		for (int j = 0; j < PENTO_SIZE; j++)
			if (p.at(i, j) != ' ')
				pb[x + i][y + j] = ' ';

	// for each remaining position, find connected neighbors
	// eliminate if number of connected neighbors < PENTO_SIZE
	for (int i = 0; i < PUZZLE_ROWS; i++)
		for (int j = 0; j < PUZZLE_COLS; j++)
			if (pb[i][j] != ' ')
			{
				vector<coord> n; // neighbors
				n.push_back(make_pair(i, j));	
				neighbors(i, j, pb, n);
				if (n.size() % PENTO_SIZE != 0)
					return false;	
			}

	return true;
}

bool puzzle::fits(pentomino p, int x, int y, vector<coord>& filled)
{
	// Does the pentomino overlap another?
	for (int i = 0; i < PENTO_SIZE; i++)
		for (int j = 0; j < PENTO_SIZE; j++)
			if (p.at(i, j) != ' ')
			{
				coord c = make_pair(x + i, y + j);
				if (find(filled.begin(), filled.end(), c) != filled.end())
					return false;	
			}	

	// Does the pentomino overflow the bounds?
	for (int i = 0; i < PENTO_SIZE; i++)
		for (int j = 0; j < PENTO_SIZE; j++)
			if (p.at(i, j) != ' ')
				if (x + i > PUZZLE_ROWS - 1 || y + j > PUZZLE_COLS - 1) 
				{
					return false;
				}

	// Does it fit?
	for (int i = 0; i < PENTO_SIZE; i++)
		for (int j = 0; j < PENTO_SIZE; j++)
			if (p.at(i, j) != ' ' && bitmap[x + i][y + j] == ' ')
			{
				return false;
			}

	// Is a solution possible with this fit?
	return eval(p, x, y, filled);
}

bool puzzle::solve(vector<pentomino>& shapes, vector<coord>& filled)
{
	if (done(filled))
		return true;

	if (shapes.empty())
		return false;

	// get first shape, s
	pentomino s = shapes.front();

	// get all orientations of s
	vector<pentomino> orient;
	s.orientations(orient);

	// for each orientation of s
	vector<pentomino>::iterator si;
	for (si = orient.begin(); si != orient.end(); si++)
	{
		// for each position in the puzzle
		for (int i = -PENTO_SIZE + 1; i < PUZZLE_ROWS + PENTO_SIZE - 1; i++)
			for (int j = -PENTO_SIZE + 1; j < PUZZLE_COLS + PENTO_SIZE - 1; j++)
			{
				if (fits(*si, i, j, filled))
				{
					// add coordinates of pentomino to extend filled 
					vector<coord> new_filled;
					vector<coord>::iterator ci;
					for (ci = filled.begin(); ci != filled.end(); ci++)
						new_filled.push_back(*ci);

					for (int u = 0; u < PENTO_SIZE; u++)
						for (int v = 0; v < PENTO_SIZE; v++)
							if ((*si).at(u, v) != ' ')
								new_filled.push_back(make_pair(i + u, j + v));

					// rest of shapes
					vector<pentomino> rest_shapes;
					for (int k = 1; k < shapes.size(); k++)
						rest_shapes.push_back(shapes.at(k));

					if (solve(rest_shapes, new_filled))
					{
						// extend partial solution
						sol.push_back(make_pair(make_pair(i, j), *si));			
						return true;
					}
				}
			}
	}

	return false;	
}

void puzzle::print_solution()
{
	puzzle_bitmap print_map;

	for (int i = 0; i < PUZZLE_ROWS; i++)
		for (int j = 0; j < PUZZLE_COLS; j++)
			print_map[i][j] = ' ';

	solution::iterator si;
	for (si = sol.begin(); si != sol.end(); si++)
	{
		coord c = (*si).first;
		pentomino p = (*si).second;
		p.print();
		cout << c.first << " " << c.second << endl;
		for (int i = 0; i < PENTO_SIZE; i++)
			for (int j = 0; j < PENTO_SIZE; j++)
				if (p.at(i, j) != ' ') { 
					cout << i << " " << j << endl;
					print_map[c.first + i][c.second + j] = 
						p.at(i, j);
				}
	}

	for (int i = 0; i < PUZZLE_ROWS; i++)
	{
		for (int j = 0; j < PUZZLE_COLS; j++)
			cout << print_map[i][j] << " ";
		cout << endl;
	}

}

int main(int argc, char **argv)
{
	vector<pentomino> shapes;

	shapes.push_back(W);
	shapes.push_back(N);
	shapes.push_back(F);
	//shapes.push_back(T);
	//shapes.push_back(Z);
	shapes.push_back(X);
	shapes.push_back(L);
	shapes.push_back(P);
	shapes.push_back(U);
	shapes.push_back(V);
	shapes.push_back(Y);
	shapes.push_back(I);

	vector<coord> filled;
	puzzle p(first_puzzle, PUZZLE_ROWS, PUZZLE_COLS, shapes);

	if (p.solve(shapes, filled))
		cout << "Solved." << endl;
	else
		cout << "No solution." << endl;

	p.print_solution();

	return 0;
}
